Problem statement: zenit17ckc

Cenné bane

Počet bodov: 15, časový limit: 1000ms

Mikx sa rozhodol, že sa dá na baníctvo. Prišiel teda na stránku svojho obľúbeného obchodu s baníckymi potrebami, otvoril záložku s grafickými kartami a začal si vyberať. Časy pre baníkov-začiatočníkov sú ale zlé a ceny sú preto vysoké. Mikx si ale všimol, že v obchode majú aj staršie, použité karty. Tieto sú oveľa lacnejšie, no aj sa rýchlejšie kazia.

Mikx teda sledoval ponuky v obchode a postupne nakupoval, aby mal grafiky aj do zásoby, keby sa mu nejaká pokazila (práca v bani nie je vôbec ľahká!). Dobre aj urobil, pretože na konci každého dňa sa mu jedna z grafík pokazila. Bola by to strašná galiba, keby ostal úplne bez grafiky – nemohol by si pozrieť najnovší diel svojho obľúbeného seriálu! Diely vychádzajú aj večer aj ráno, nemôže si dovoliť nič zmeškať, inak by sa stratil v deji.

Na konci mesiaca mal siahodlhý dokument s históriou cien. Pomôžte mu z dokumentu zistiť, ako najlacnejšie vedel nakúpiť.

Vstup a výstup

V prvom riadku je číslo \(n\) – počet dní, počas ktorých Mikx obchodoval. V druhom riadku je číslo \(g\) – počet grafických kariet v katalógu obchodu.

Nasleduje \(n \cdot g\) riadkov. Každých \(g\) riadkov opisuje ceny grafík pre \(i\)-ty deň. Platí \(1 \leq n, g \leq 100\). Ceny grafík neprekročia \(1000\).

Na výstupe vypíšte jedno číslo – najmenšiu sumu, ktorú musel zaplatiť, aby nikdy neostal bez grafiky.

Príklady

Input:

2 2
1
2
100
200

Output:

2

Mikx si v prvý deň kúpi dva kusy prvej grafickej karty, čo ho bude stáť 2. Jedna sa mu v ten večer pokazí, a druhá mu vystačí na ďalší deň